
// leetcode 215. 数组中的第K个最大元素
//class Solution {
//    public int findKthLargest(int[] nums, int k) {
//        // 堆堆堆
//        PriorityQueue<Integer> heap = new PriorityQueue<>();
//        for (int i = 0; i < k; i++) {
//            heap.offer(nums[i]);
//        }
//        for (int i = k; i < nums.length; i++) {
//            if (heap.peek() < nums[i]) {
//                heap.poll();
//                heap.offer(nums[i]);
//            }
//        }
//        return heap.peek();
//    }
//}


// leetcode 347. 前 K 个高频元素
//class Solution {
//    public int[] topKFrequent(int[] nums, int k) {
//        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<>() {
//            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//                return o1.getValue() - o2.getValue();
//            }
//        });
//        Map<Integer, Integer> hash = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            int count = hash.getOrDefault(nums[i], 0);
//            hash.put(nums[i], count + 1);
//        }
//        int count = 0;
//        for (Map.Entry<Integer, Integer> x : hash.entrySet()) {
//            if (count < k) {
//                queue.offer(x);
//                count++;
//            } else {
//                if (queue.peek().getValue() < x.getValue()) {
//                    queue.poll();
//                    queue.offer(x);
//                }
//            }
//        }
//        int[] ret = new int[k];
//        for (int i = 0; i < k; i++) {
//            ret[i] = queue.poll().getKey();
//        }
//        return ret;
//
//    }
//}

// leetcode 295. 数据流的中位数
//class MedianFinder {
//    // 中位数，较小数组的最大值，较大数组的最小值
//    // 一半较小数组元素比较大数组元素多1
//    PriorityQueue<Integer> saveMin;
//    PriorityQueue<Integer> saveMax;
//
//    public MedianFinder() {
//        saveMin = new PriorityQueue<>(new Comparator<>() {
//            public int compare(Integer o1, Integer o2) {
//                return o2 - o1;
//            }
//        });
//        saveMax = new PriorityQueue<>();
//    }
//
//    public void addNum(int num) {
//        saveMax.offer(num);
//        saveMin.offer(saveMax.poll());
//        if (saveMin.size() > saveMax.size() + 1) {
//            saveMax.offer(saveMin.poll());
//        }
//    }
//
//    public double findMedian() {
//        int minSize = saveMin.size();
//        int maxSize = saveMax.size();
//        if ((maxSize + minSize) % 2 == 0) {
//            return (saveMin.peek() + saveMax.peek()) / 2.0;
//        } else {
//            return saveMin.peek() * 1.0;
//        }
//    }
//}